package searchBack;

import java.util.ArrayList;
import java.util.List;

/**
 * 该包文件下是回溯的算法的一些代码实现
 *
 * 此类是指全排列问题
 */
public class fullPermute {
    public static void main(String[] args) {
        solutionFullPermute p = new solutionFullPermute();
        int[] nums = new int[]{1, 2, 3, 4};
        List<List<Integer>> res = p.permute(nums);

        System.out.printf(res.toString());
    }

}

/**
 * 具体代码实现
 */
class solutionFullPermute{
    // 用来存放已经找出的匹配的值
    List<List<Integer>> res = new ArrayList<>();

    /**
     * 主函数
     * @param nums 传入的数字列
     */
    public List<List<Integer>> permute(int[] nums){
        List<Integer> tracks = new ArrayList<>();
        backTrack(nums, tracks);
        return res;
    }

    /**
     * 全排列函数
     * @param nums     元素列表
     * @param tracks   存放匹配过的元素
     */
    public void backTrack(int[] nums, List<Integer> tracks){
        // 所有元素都存在了就填入匹配列表中
        if(tracks.size() == nums.length){
            System.out.println(tracks.toString());
            res.add(new ArrayList<>(tracks));
        }

        for(int i=0; i<nums.length; i++){
            int tmp = nums[i];
            // 当这个元素已经被遍历过就直接跳过
            if(tracks.contains(tmp)){
                continue;
            }

            // 这个元素没出现过放入 tracks 中
            tracks.add(tmp);
            backTrack(nums, tracks);
            // 这个元素遍历完了，回溯到这个匹配这个元素之前的状态，所有将这个元素抹去
            tracks.remove(tracks.size()-1);
        }
    }
}

